import org.junit.jupiter.api.Test;

import java.util.HashSet;
import java.util.IllegalFormatCodePointException;
import java.util.Set;
import java.util.TreeSet;

/**
 * 滑动窗口的原理：当我们知道子串[i,j)是无重复子串，此时再加入一个字符的话,我们只需要判断子串[i,j)里面
 * 是否包含j就可以了，要是重复了，就把窗口里面重复的元素去掉，因为要是有重复的话，要想得到不重复的子串，、
 * 只能从第一个重复的字符后面开始取，要是不重复的话，就把字符j加到窗口中，更新此时最大无重读子串的长度为[right-left+1]
 * 然后将right往后移，之后字符串结束
 */
public class _03_无重复字符的最长子串_滑动窗口 {

    @Test
    void test(){

        System.out.println(lengthOfLongestSubstring1("aasdasda"));
    }

    public int lengthOfLongestSubstring1(String s) {
        int length=s.length();
        if (length<=1){
            return length;
        }
        int maxLen=1;
        //定义滑动窗口的左边界和有边界
        int left=0,right=0;
        //创建窗口
        Set<Character> window=new TreeSet<>();
        while (right<length){
            //获取要判断的字符j
            char c = s.charAt(right);
            //判断窗口是否包含字符
            while (window.contains(c)){
                //要是重复的话，就去掉窗口中重复字符之前的元素
                window.remove(s.charAt(left));
                //左边界右移，此时还要去判断重复值是否还在window里面，所以这里要使用while循环判断
                left++;
            }
            //将字符放进窗口里面
            window.add(s.charAt(right));
            //更新最大长度的值
            maxLen=Math.max(maxLen,right-left+1);
            //右节点右移
            right++;
        }
        return maxLen;
    }


}
